import java.util.ArrayList;
import java.util.List;

class Solution5 {

    List<Integer> path;
    List<List<Integer>> ret;
    int aim;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        path = new ArrayList<>();
        ret = new ArrayList<>();
        aim = target;

        dfs(candidates, 0, 0);
        return ret;
    }

    public void dfs(int[] candidates, int pos, int sum){
        if(sum == aim){
            ret.add(new ArrayList<>(path));
            return ;
        }
        if(sum > aim || pos == candidates.length){
            return ;
        }

        for(int k = 0; k * candidates[pos] + sum <= aim; k++){
            if(k != 0) { path.add(candidates[pos]);}
            dfs(candidates, pos + 1, sum + k * candidates[pos]);
        }

        //恢复现场
        for(int k = 1; k * candidates[pos] + sum <= aim; k++){
            path.remove(path.size() - 1);
        }
    }
}